class Solution {
public:
    /*
     * @param nums: A list of integers
     * @return: An integer denotes the sum of max two non-overlapping subarrays
     */
    int maxTwoSubArrays(vector<int> &nums) {
        // write your code here
	    int len = nums.size();
        if( len == 0 || len  == 1 )
            return 0;

        vector<int> left(len, 0);
        vector<int> right(len, 0);
        
        int leftmax = INT_MIN, rightmax = INT_MIN;
        int leftsum = 0, rightsum = 0;
        for(int i = 0; i < len - 1; i++){
            leftsum += nums[i];
            if( leftsum > leftmax )
                leftmax = leftsum;
            if( leftsum < 0 )
                leftsum = 0;
            left[i] = leftmax;
        }

        for( int j = len - 1; j > 0; j-- ){
            rightsum += nums[j];
            if( rightsum > rightmax )
                rightmax = rightsum;
            if( rightsum < 0 )
                rightsum = 0;
            right[j] = rightmax;
        }

        int result = INT_MIN;
        for(int k = 0; k <= len - 2; k++){
            result = max(result, left[k] + right[k+1]);
        }

        return result;
    }
};

